SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Programmation dynamique</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading">Programmation dynamique</h1>

</header>

</div>

En <a href="Informatique" title="Informatique">informatique</a>, la programmation dynamique est une méthode <a href="Algorithme" title="Algorithme">algorithmique</a> pour résoudre des <a href="Optimisation_(math%C3%A9matiques)" title="Optimisation (mathématiques)">problèmes d'optimisation</a>. Le concept a été introduit au début des années 1950 par <a href="Richard_Bellman" title="Richard Bellman">Richard Bellman</a><a href="#cite_note-Cormen359-1">[1]</a>. À l'époque, le terme « programmation » signifie planification et ordonnancement<a href="#cite_note-Cormen359-1">[1]</a>. La programmation dynamique consiste à résoudre un problème en le décomposant en sous-problèmes, puis à résoudre les sous-problèmes, des plus petits aux plus grands en stockant les résultats intermédiaires. Elle a d'emblée connu un grand succès, car de nombreuses fonctions économiques de l'industrie étaient de ce type, comme la conduite et l'optimisation de procédés chimiques, ou la gestion de stocks<a href="#cite_note-Cormen359-1">[1]</a>.

<div class="mw-heading mw-heading2"><h2 id="Principe">Principe</h2></div>

Illustrons la programmation dynamique sur le calcul du nème terme de la <a href="Suite_de_Fibonacci" title="Suite de Fibonacci">suite de Fibonacci</a>, parfois utilisé comme exemple introductif dans un cours sur la programmation dynamique<a href="#cite_note-2">[2]</a>. La suite de Fibonacci est définie par F0 = 0, F1 = 1 et Fn = Fn-1 + Fn-2. La programmation dynamique s'appuie sur le principe d'optimalité de Bellman : une solution optimale d'un problème s'obtient en combinant des solutions optimales à des sous-problèmes. Sur l'exemple de la suite de Fibonacci, la solution Fn s'obtient en additionnant Fn-1 et Fn-2.

La méthode de programmation dynamique, comme la méthode <a href="Diviser_pour_r%C3%A9gner_(informatique)" title="Diviser pour régner (informatique)">diviser pour régner</a>, résout des problèmes en combinant des solutions de sous-problèmes. Les algorithmes diviser-pour-régner partitionnent le problème en sous-problèmes indépendants qu’ils résolvent <a href="R%C3%A9cursivit%C3%A9" title="Récursivité">récursivement</a>, puis combinent leurs solutions pour résoudre le problème initial. La méthode diviser-pour-régner est inefficace si on doit résoudre plusieurs fois le même sous-problème. Par exemple, l'algorithme suivant est inefficace :

<pre>fonction fibonacci(n)

si n = 0 ou n = 1

retourner n

sinon

retourner fibonacci(n-1) + fibonacci(n-2)

</pre>

Le <a href="D%C3%A9pendance_fonctionnelle" title="Dépendance fonctionnelle">graphe de dépendance</a> montré sur la droite n'est pas un <a href="Arbre_(th%C3%A9orie_des_graphes)" title="Arbre (théorie des graphes)">arbre</a> : cela illustre que les sous-problèmes se chevauchent. Par exemple, pour calculer F5, nous avons besoin de F3 et F4. Mais pour calculer F4, nous avons besoin de F2 et F3. Ainsi, F3 est utile à la fois pour le calcul de F4 et pour le calcul de F5. La programmation dynamique consiste alors à stocker les valeurs des sous-problèmes pour éviter les recalculs<a href="#cite_note-Cormen-3">[3]</a>. Il existe alors deux méthodes pour calculer effectivement une solution : la méthode ascendante et la méthode descendante. Dans la méthode ascendante, on commence par calculer des solutions pour les sous-problèmes les plus petits, puis, de proche en proche, on calcule les solutions des problèmes en utilisant le principe d'optimalité et on mémorise les résultats dans un tableau F[.]. Par exemple :

<pre>fonction fibonacci(n)

F[0] = 0

F[1] = 1

pour tout i de 2 à n

F[i] := F[i-1] + F[i-2]

retourner F[n]

</pre>

Dans la méthode descendante, on écrit un <a href="Algorithme_r%C3%A9cursif" title="Algorithme récursif">algorithme récursif</a> mais on utilise la <a href="M%C3%A9mo%C3%AFsation" title="Mémoïsation">mémoïsation</a> pour ne pas résoudre plusieurs fois le même problème, c'est-à-dire que l'on stocke dans un tableau F[.] les résultats des appels récursifs :

<pre>fonction fibonacci(n)

si F[n] n'est pas défini

si n = 0 ou n = 1

F[n] := n

sinon

F[n] := fibonacci(n-1) + fibonacci(n-2)

retourner F[n]

</pre>

La programmation dynamique est utilisée pour résoudre des problèmes d'optimisation. Les sections suivantes en donnent quelques exemples. La conception d’un algorithme de programmation dynamique est typiquement découpée en quatre étapes<a href="#cite_note-Cormen-3">[3]</a>.

<ol><li>Caractériser la structure d’une solution optimale.</li>

<li>Définir (souvent de manière récursive) la valeur d’une solution optimale.</li>

<li>Calculer la valeur d’une solution optimale.</li>

<li>Construire une solution optimale à partir des informations calculées.</li></ol>

La dernière étape est utile pour calculer une solution optimale, et pas seulement la valeur optimale. Un problème d'optimisation peut avoir de nombreuses solutions. Chaque solution a une valeur, et on souhaite trouver une solution ayant la valeur optimale. Une telle solution optimale au problème n'est pas forcément unique, c'est sa valeur qui l'est.

<div class="mw-heading mw-heading2"><h2 id="Exemples">Exemples</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Pyramide_de_nombres">Pyramide de nombres</h3></div>

Dans une pyramide de nombres, on cherche, en partant du sommet de la pyramide, et en se dirigeant vers le bas à chaque étape, à maximiser le total des nombres traversés<a href="#cite_note-4">[4]</a>. Dans l'exemple ci-dessous, le maximum est obtenu pour le chemin en gras (3+7+4+9 = 23).

<pre> 3

7 4

2 4 6

9 5 9 3

</pre>

Un algorithme naïf, sur l'exemple, consiste à examiner les 8 chemins possibles, et choisir celui qui a le plus grand total. En général, quand la pyramide a n niveaux, il y a <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{n-1}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{n-1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/80c2cb3e3a7de902c9503fb34a17641df5896539.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.481ex; height:2.676ex;" alt="{\displaystyle 2^{n-1}}" loading="lazy"> chemins et <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{n}-2}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{n}-2}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8701ed19e403e49799daf0dc76f21fcccfbf8d4f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.384ex; height:2.509ex;" alt="{\displaystyle 2^{n}-2}" loading="lazy"> calculs à effectuer. Donc l'algorithme naïf est en temps exponentiel en n.

Le paradigme de la programmation dynamique permet d'obtenir un algorithme efficace en définissant des sous-problèmes, en écrivant une <a href="Suite_d%C3%A9finie_par_r%C3%A9currence" title="Suite définie par récurrence">relation de récurrence</a>, puis en donnant un algorithme (avec méthode ascendante ou descendante).

Pour toute position <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> dans la pyramide, notons <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v(x)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b371a381e15c71d8fc4ec43cf14b156f02a0d35a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.267ex; height:2.843ex;" alt="{\displaystyle v(x)}" loading="lazy"> le nombre écrit à cette position et <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c(x)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b20e1deb5bbfe90c658811e9635d865f02902791.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.146ex; height:2.843ex;" alt="{\displaystyle c(x)}" loading="lazy"> la somme des nombres traversés dans un chemin maximal issu de <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy">. Les sous-problèmes consistent à calculer les valeurs de <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c(x)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b20e1deb5bbfe90c658811e9635d865f02902791.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.146ex; height:2.843ex;" alt="{\displaystyle c(x)}" loading="lazy"> pour tout <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy">. Le problème initial consiste à calculer <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c(x)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b20e1deb5bbfe90c658811e9635d865f02902791.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.146ex; height:2.843ex;" alt="{\displaystyle c(x)}" loading="lazy"> lorsque <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> est le sommet de la pyramide.

Donnons maintenant une définition récursive de <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c(x)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b20e1deb5bbfe90c658811e9635d865f02902791.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.146ex; height:2.843ex;" alt="{\displaystyle c(x)}" loading="lazy"> :

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c(x)=v(x)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a247b7823c12687a4201ad904cc04a5bfb84a7b1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.511ex; height:2.843ex;" alt="{\displaystyle c(x)=v(x)}" loading="lazy"> pour toute position <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> située au rez-de chaussée de la pyramide</dd>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c(x)=v(x)+\max(c(g(x)),c(d(x)))}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ceed95464670be73a92b96d947c4ec5dff7a8d65.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:35.762ex; height:2.843ex;" alt="{\displaystyle c(x)=v(x)+\max(c(g(x)),c(d(x)))}" loading="lazy"> pour toute autre position <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy">, où <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g(x)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c6ca91363022bd5e4dcb17e5ef29f78b8ef00b59.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.255ex; height:2.843ex;" alt="{\displaystyle g(x)}" loading="lazy"> et <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d(x)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c74c31c749da4bca087f03265cda1e09b0f26cb7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.355ex; height:2.843ex;" alt="{\displaystyle d(x)}" loading="lazy"> sont les positions inférieures gauche et droite sous la position <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy">.</dd></dl>

Si on cherche à calculer directement par la définition récursive, on évalue plusieurs fois la même valeur : dans l'exemple ci-dessus, la valeur 4 de la troisième ligne est calculée deux fois en venant de la ligne supérieure (une fois depuis le 7, une fois depuis le 4). Le paradigme de la programmation dynamique consiste à calculer les valeurs <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c(x)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b20e1deb5bbfe90c658811e9635d865f02902791.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.146ex; height:2.843ex;" alt="{\displaystyle c(x)}" loading="lazy">, soit à l'aide d'un algorithme itératif ascendant en stockant les valeurs déjà calculées dans un tableau, soit à l'aide d'un algorithme récursif descendant avec <a href="M%C3%A9mo%C3%AFsation" title="Mémoïsation">mémoïsation</a>. L'important est de conserver dans un tableau les valeurs intermédiaires. La séquence des calculs est indiquée en gras :

<pre> 3 23

7 4 20 19 20 19

2 4 6 11 13 15 11 13 15

9 5 9 3 9 5 9 3

</pre>

Le nombre de calculs est seulement <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n(n-1)/2}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n(n-1)/2}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5b1d96c185de1bffc1e78739934b09489f683efc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.926ex; height:2.843ex;" alt="{\displaystyle n(n-1)/2}" loading="lazy">.

<div class="mw-heading mw-heading3"><h3 id="Calcul_d'un_produit_de_matrices">Calcul d'un produit de matrices</h3></div>

On se donne des <a href="Matrice_(math%C3%A9matiques)" title="Matrice (mathématiques)">matrices</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M_{1},M_{2},\ldots ,M_{h}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M_{1},M_{2},\ldots ,M_{h}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6b62ad918f8651173d83b53eb5205544e69c1549.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:16.262ex; height:2.509ex;" alt="{\displaystyle M_{1},M_{2},\ldots ,M_{h}}" loading="lazy">, et on veut calculer la matrice produit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M_{1}M_{2}\cdots M_{h}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M_{1}M_{2}\cdots M_{h}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/30e31f4bd562b3abcfefcd69eb4f6fcc37cf3bd8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:13.547ex; height:2.509ex;" alt="{\displaystyle M_{1}M_{2}\cdots M_{h}}" loading="lazy"><a href="#cite_note-5">[5]</a>,<a href="#cite_note-Cormen-3">[3]</a>. Les matrices ne sont pas forcément carrées, et l'ordre dans lequel on effectue les multiplications peut influencer le coût. Ainsi, le produit des matrices <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A_{4\times 5}.B_{5\times 8}.C_{8\times 5}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A_{4\times 5}.B_{5\times 8}.C_{8\times 5}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5b165f5888b6b18bc0333ebc69f56acdf46a3b50.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:16.701ex; height:2.509ex;" alt="{\displaystyle A_{4\times 5}.B_{5\times 8}.C_{8\times 5}}" loading="lazy"> exige un nombre de multiplications différent suivant que l'on débute par <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (A_{4\times 5}.B_{5\times 8}).C_{8\times 5}=M_{4\times 8}.C_{8\times 5}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (A_{4\times 5}.B_{5\times 8}).C_{8\times 5}=M_{4\times 8}.C_{8\times 5}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0d4790436b9c9c0358d9383915b551da2436998c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:32.868ex; height:2.843ex;" alt="{\displaystyle (A_{4\times 5}.B_{5\times 8}).C_{8\times 5}=M_{4\times 8}.C_{8\times 5}}" loading="lazy">, avec 320 multiplications, ou par <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A_{4\times 5}.(B_{5\times 8}.C_{8\times 5})=A_{4\times 5}.N_{5\times 5}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A_{4\times 5}.(B_{5\times 8}.C_{8\times 5})=A_{4\times 5}.N_{5\times 5}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8363791bb9803066621c0e5a84a8909a84302b67.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:32.562ex; height:2.843ex;" alt="{\displaystyle A_{4\times 5}.(B_{5\times 8}.C_{8\times 5})=A_{4\times 5}.N_{5\times 5}}" loading="lazy">, avec 300 multiplications. La seconde façon est optimale par rapport au nombre de multiplications.

Si chaque matrice <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M_{i}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/eda8fd06f1cd5de22ed07385a0f8aa19773b2de9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.054ex; height:2.509ex;" alt="{\displaystyle M_{i}}" loading="lazy"> a <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m_{i}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/95ec8e804f69706d3f5ad235f4f983220c8df7c2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.84ex; height:2.009ex;" alt="{\displaystyle m_{i}}" loading="lazy"> lignes et <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m_{i+1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m_{i+1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f02a452aa28b61b8ea71eb6ee7c46d448ce70fb3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.941ex; height:2.009ex;" alt="{\displaystyle m_{i+1}}" loading="lazy"> colonnes, le produit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M_{i-1}M_{i}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M_{i-1}M_{i}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4e96457fadcfbe96da2f7ade4b09c437a7ddf8ec.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.208ex; height:2.509ex;" alt="{\displaystyle M_{i-1}M_{i}}" loading="lazy"> demande <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(m_{i-1}m_{i}m_{i+1})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(m_{i-1}m_{i}m_{i+1})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d0b9b1775e87c78adbb6219fbd0514371dca61b1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.304ex; height:2.843ex;" alt="{\displaystyle O(m_{i-1}m_{i}m_{i+1})}" loading="lazy"> opérations. On note <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c_{i,j}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c_{i,j}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8504228ae66c6c24cc403c35a3df8d78771c9492.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.941ex; height:2.343ex;" alt="{\displaystyle c_{i,j}}" loading="lazy"> le nombre minimum d'opérations pour calculer le produit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M_{i}\cdots M_{j}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M_{i}\cdots M_{j}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/93cc9dced16f1bf6acfbaabf1b04e4bde0d20076.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:9.715ex; height:2.843ex;" alt="{\displaystyle M_{i}\cdots M_{j}}" loading="lazy">. On a alors

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c_{i,i}=0,c_{i-1,i}=m_{i-1}m_{i}m_{i+1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8e00ed3ba64b9bd0ed6b726b3d317dbf2b4e3158.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:28.878ex; height:2.843ex;" alt="{\displaystyle c_{i,i}=0,c_{i-1,i}=m_{i-1}m_{i}m_{i+1}}" loading="lazy">.</dd></dl>

Pour obtenir la meilleure valeur pour le produit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M_{i}\cdots M_{j}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M_{i}\cdots M_{j}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/93cc9dced16f1bf6acfbaabf1b04e4bde0d20076.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:9.715ex; height:2.843ex;" alt="{\displaystyle M_{i}\cdots M_{j}}" loading="lazy">, on le découpe en <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M_{i}\cdots M_{k}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M_{i}\cdots M_{k}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/35ea9f96e2c0d3b9f848d87263f90ee836523c35.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.894ex; height:2.509ex;" alt="{\displaystyle M_{i}\cdots M_{k}}" loading="lazy"> et <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M_{k+1}\cdots M_{j}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M_{k+1}\cdots M_{j}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7567bccb3a636c9458faba6d7136026004d5e6c8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:12.105ex; height:2.843ex;" alt="{\displaystyle M_{k+1}\cdots M_{j}}" loading="lazy"> et on choisit le meilleur <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy">. Ceci conduit à la formule :

<msub>

</mrow>

</msub>

</mrow>

</munder>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c_{i,j}=\min _{i\leq k<j}[c_{i,k}+c_{k+1,j}+m_{i}m_{k+1}m_{j+1}]}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/bf9b2275fe4e66e4fc674b7aafe1952d99271b94.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.338ex; width:39.244ex; height:4.343ex;" alt="{\displaystyle c_{i,j}=\min _{i\leq k<j}[c_{i,k}+c_{k+1,j}+m_{i}m_{k+1}m_{j+1}]}" loading="lazy">.</dd></dl>

Le calcul des <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c_{i,j}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c_{i,j}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8504228ae66c6c24cc403c35a3df8d78771c9492.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.941ex; height:2.343ex;" alt="{\displaystyle c_{i,j}}" loading="lazy"> se fait dans un tableau, diagonale par diagonale, en temps quadratique en le nombre de matrices.

Dans cet exemple aussi, il est important de garder le résultat des calculs dans un tableau pour ne pas les recalculer.

<div class="mw-heading mw-heading2"><h2 id="Histoire">Histoire</h2></div>

Le terme programmation dynamique était utilisé dans les <a href="Ann%C3%A9es_1940" title="Années 1940">années 1940</a> par <a href="Richard_Bellman" title="Richard Bellman">Richard Bellman</a> pour décrire le processus de résolution de problèmes où on trouve les meilleures décisions les unes après les autres. En 1953, il en donne la définition moderne, où les décisions à prendre sont ordonnées par sous-problèmes<a href="#cite_note-6">[6]</a> et le domaine a alors été reconnu par <a href="IEEE" class="mw-redirect" title="IEEE">IEEE</a> comme un sujet d'analyse de systèmes et d’ingénierie. La contribution de Bellman est connu sous le nom d'équation de Bellman, qui présente un problème d'optimisation sous forme récursive.

Bellman explique l'idée du terme programmation dynamique dans son autobiographie, Eye of the Hurricane: An Autobiography <a href="#cite_note-7">[7]</a>. Il dit :

« I spent the Fall quarter (of 1950) at RAND. My first task was to find a name for multistage decision processes. An interesting question is, Where did the name, dynamic programming, come from? The 1950s were not good years for mathematical research. We had a very interesting gentleman in Washington named <a href="Charles_Erwin_Wilson" title="Charles Erwin Wilson">Wilson</a>. He was Secretary of Defense, and he actually had a pathological fear and hatred of the word research. I’m not using the term lightly; I’m using it precisely. His face would suffuse, he would turn red, and he would get violent if people used the term research in his presence. You can imagine how he felt, then, about the term mathematical. The RAND Corporation was employed by the Air Force, and the Air Force had Wilson as its boss, essentially. Hence, I felt I had to do something to shield Wilson and the Air Force from the fact that I was really doing mathematics inside the RAND Corporation. What title, what name, could I choose? In the first place I was interested in planning, in decision making, in thinking. But planning, is not a good word for various reasons. I decided therefore to use the word “programming”. I wanted to get across the idea that this was dynamic, this was multistage, this was time-varying. I thought, let's kill two birds with one stone. Let's take a word that has an absolutely precise meaning, namely dynamic, in the classical physical sense. It also has a very interesting property as an adjective, and that it's impossible to use the word dynamic in a pejorative sense. Try thinking of some combination that will possibly give it a pejorative meaning. It's impossible. Thus, I thought dynamic programming was a good name. It was something not even a Congressman could object to. So I used it as an umbrella for my activities. »

</blockquote>

L'adjectif dynamique était donc choisi par Bellman pour insister sur l'aspect temporel des problèmes, et parce que le terme impressionnait<a href="#cite_note-Eddy-8">[8]</a>. Le mot programmation référait à l'utilisation d'une méthode pour trouver un programme optimal dans un sens militaire : emploi du temps ou de la logistique. D'ailleurs, l'usage est le même que dans les termes <a href="Optimisation_lin%C3%A9aire" title="Optimisation linéaire">programmation linéaire</a> et programmation mathématique, synonyme pour optimisation mathématique<a href="#cite_note-9">[9]</a>.

Mais cette explication est controversée. Selon le <a href="Intelligence_artificielle_%3A_une_approche_moderne" title="Intelligence artificielle : une approche moderne">livre Artificial Intelligence: A Modern Approach</a> de <a href="Stuart_Russell" title="Stuart Russell">Russell</a> et <a href="Peter_Norvig" title="Peter Norvig">Norvig</a><a href="#cite_note-10">[10]</a>, l'explication ci-dessus n'est pas tout à fait vraie car le premier article de 1952 où Bellman utilise le terme programmation dynamique a paru avant que <a href="Charles_Erwin_Wilson" title="Charles Erwin Wilson">Wilson</a> devienne secrétaire de la défense en 1953. Aussi, dans un discours de <a href="Harold_J._Kushner" title="Harold J. Kushner">Harold J. Kushner</a><a href="#cite_note-11">[11]</a>, il dit de Bellman : « On the other hand, when I asked him the same question, he replied that he was trying to upstage Dantzig's linear programming by adding dynamic. Perhaps both motivations were true. »

<div class="mw-heading mw-heading2"><h2 id="Applications_algorithmiques">Applications algorithmiques</h2></div>

<ul><li>Le <a href="Probl%C3%A8me_du_plus_court_chemin" class="mw-redirect" title="Problème du plus court chemin">problème du plus court chemin</a> (<a href="Algorithme_de_Bellman-Ford" title="Algorithme de Bellman-Ford">algorithme de Bellman-Ford</a> et <a href="Algorithme_de_Floyd-Warshall" title="Algorithme de Floyd-Warshall">algorithme de Floyd-Warshall</a>) ;</li>

<li><a href="Probl%C3%A8me_d'affectation" title="Problème d'affectation">Problème d'affectation</a> des ressources. Il s'agit (par exemple) de distribuer m skis à n skieurs (m>n) en minimisant les écarts de taille entre les skis et les skieurs. La propriété d'optimalité des sous-structures (si une distribution est optimale, alors toute sous-partie des skis et des skieurs est optimale) le rend traitable par programmation dynamique[réf. nécessaire] ;</li>

<li>Le <a href="Probl%C3%A8me_du_sac_%C3%A0_dos" title="Problème du sac à dos">problème du sac à dos</a> (knapsack en anglais) est un problème classique de <a href="Recherche_op%C3%A9rationnelle" title="Recherche opérationnelle">recherche opérationnelle</a> qui est <a href="Complexit%C3%A9_en_temps" title="Complexité en temps">NP-difficile</a>, mais qui est résolu de manière <a href="Algorithme_pseudo-polynomial" class="mw-redirect" title="Algorithme pseudo-polynomial">pseudo-polynomiale</a> à l'aide d'un algorithme de programmation dynamique ;</li>

<li>Le <a href="Probl%C3%A8me_du_rendu_de_monnaie" title="Problème du rendu de monnaie">problème du rendu de monnaie</a> dans le cas général ;</li>

<li>La recherche de la <a href="Plus_longue_sous-suite_strictement_croissante" title="Plus longue sous-suite strictement croissante">plus longue sous-suite strictement croissante</a> dans une suite de nombres ;</li>

<li>Des problèmes d'<a href="Algorithmique_du_texte" title="Algorithmique du texte">algorithmique du texte</a> comme le calcul de la plus longue sous-suite commune entre deux chaînes[réf. nécessaire], le calcul de la <a href="Distance_de_Levenshtein" title="Distance de Levenshtein">distance de Levenshtein</a> ou encore l'<a href="Alignement_de_s%C3%A9quences" title="Alignement de séquences">alignement de séquences</a> (avec l'<a href="Algorithme_de_Smith-Waterman" title="Algorithme de Smith-Waterman">algorithme de Smith-Waterman</a> par exemple) ;</li>

<li>L'<a href="Algorithme_de_Cocke-Younger-Kasami" title="Algorithme de Cocke-Younger-Kasami">algorithme CYK</a> est un algorithme d'<a href="Analyse_syntaxique" title="Analyse syntaxique">analyse syntaxique</a> ;</li>

<li>La méthode la plus utilisée pour résoudre le problème de <a href="D%C3%A9tection_de_ruptures" title="Détection de ruptures">détection de ruptures</a> est la <a href="D%C3%A9tection_de_ruptures#Programmation_dynamique" title="Détection de ruptures">programmation dynamique</a>.</li>

<li>L'<a href="Algorithme_de_Viterbi" title="Algorithme de Viterbi">algorithme de Viterbi</a>, utilisé en <a href="Reconnaissance_automatique_de_la_parole" title="Reconnaissance automatique de la parole">reconnaissance de la parole</a> et dans différents problèmes de reconnaissance utilisant des <a href="Mod%C3%A8le_de_Markov_cach%C3%A9" title="Modèle de Markov caché">modèles de Markov cachés</a>.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Connexions">Connexions</h2></div>

La programmation dynamique a des liens avec le <a href="Calcul_des_variations" title="Calcul des variations">calcul des variations</a> et la <a href="Commande_optimale" title="Commande optimale">commande optimale</a>.

Un théorème général énonce que tout algorithme de programmation dynamique peut se ramener à la recherche du plus court chemin dans un graphe<a href="#cite_note-12">[12]</a>. Or, les techniques de recherche heuristique basées sur l'<a href="Algorithme_A*" title="Algorithme A*">algorithme A*</a> permettent d'exploiter les propriétés spécifiques d'un problème pour gagner en temps de calcul. Autrement dit, il est souvent plus avantageux d'exploiter un algorithme A* que d'utiliser la programmation dynamique.

<div class="mw-heading mw-heading2"><h2 id="Programmation_dynamique_et_apprentissage_par_renforcement">Programmation dynamique et apprentissage par renforcement</h2></div>

<div class="mw-heading mw-heading2"><h2 id="Notes_et_références">Notes et références</h2></div>

<li id="cite_note-Cormen359-1"><a href="#Cormen2fr">Cormen et al., Introduction à l'algorithmique</a>, <abbr class="abbr" title="page(s)">p.</abbr> 359.

</li>

<li id="cite_note-2"><a href="#cite_ref-2">↑</a> <abbr class="abbr indicateur-langue" title="Langue : anglais">(en)</abbr> « <a rel="nofollow" class="external text" href="https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/lecture-19-dynamic-programming-i-fibonacci-shortest-paths/"><cite style="font-style:normal;" lang="en">Cours du MIT sur la programmation dynamique</cite></a> ».

</li>

<li id="cite_note-Cormen-3"><a href="#Cormen2fr">Cormen et al., Introduction à l'algorithmique</a>, <abbr class="abbr" title="page(s)">p.</abbr> 315-316.

</li>

<li id="cite_note-4"><a href="#cite_ref-4">↑</a> <a href="#opc">Openclassrooms</a>.

</li>

<li id="cite_note-5"><a href="#cite_ref-5">↑</a> <a href="#Cori">Cori</a>.

</li>

<li id="cite_note-6"><a href="#cite_ref-6">↑</a> <abbr class="abbr indicateur-format format-pdf" title="Document au format Portable Document Format (PDF)">[PDF]</abbr> Stuart Dreyfus, <a rel="nofollow" class="external text" href="https://web.archive.org/web/20050110161049/http://www.wu-wien.ac.at/usr/h99c/h9951826/bellman_dynprog.pdf">« Richard Bellman on the birth of Dynamical Programming »</a>.

</li>

<li id="cite_note-7"><a href="#cite_ref-7">↑</a> Richard Bellman, Eye of the Hurricane: An Autobiography , 1984, <abbr class="abbr" title="page">p.</abbr> 159.

</li>

<li id="cite_note-Eddy-8"><a href="#cite_ref-Eddy_8-0">↑</a> Eddy, S. R., What is dynamic programming?, Nature Biotechnology, 22, 909–910, 2004.

</li>

<li id="cite_note-9"><a href="#cite_ref-9">↑</a> Nocedal, J.; Wright, S. J.: Numerical Optimization, page 9, Springer, 2006.

</li>

<li id="cite_note-10"><a href="#cite_ref-10">↑</a> Russell, S. and Norvig, P., Artificial Intelligence: A Modern Approach, 3rd edition, Prentice Hall, 2009.

</li>

<li id="cite_note-11"><a href="#cite_ref-11">↑</a> <a rel="nofollow" class="external text" href="http://a2c2.org/awards/richard-e-bellman-control-heritage-award/2004-00-00t000000/harold-j-kushner">Harold J. Kushner</a>.

</li>

<li id="cite_note-12"><a href="#cite_ref-12">↑</a> A. Martelli, « An application of heuristic search methods to edge and contour detection », Comm. ACM, 19(2):73--83, février 1976.

</li>

</ol></div>

</div>

<div class="mw-heading mw-heading2"><h2 id="Bibliographie">Bibliographie</h2></div>

<dl><dt>Ouvrages historiques</dt></dl>

<ul><li><a href="Richard_Bellman" title="Richard Bellman">Richard Bellman</a>, <cite class="italique">Dynamic Programming</cite>, Princeton, <a href="Princeton_University_Press" title="Princeton University Press">Princeton University Press</a>, <time>1957</time><span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Dynamic+Programming&rft.place=Princeton&rft.pub=Princeton+University+Press&rft.aulast=Bellman&rft.aufirst=Richard&rft.date=1957&rfr_id=info%3Asid%2Ffr.wikipedia.org%3AProgrammation+dynamique">. — Réimpression 2003, Dover Publication, Mineola, New-York, (<a href="International_Standard_Book_Number" title="International Standard Book Number">ISBN</a> 0-486-42809-5).</li>

<li>Stuart Dreyfus, « <cite style="font-style:normal">Richard Bellman on the birth of Dynamic Programming</cite> », Operations Research, <abbr class="abbr" title="volume">vol.</abbr> 50, <abbr class="abbr" title="numéro">no</abbr> 1,‎ <time class="nowrap" datetime="2002" data-sort-value="2002">janvier-février 2002</time>, <abbr class="abbr" title="pages">p.</abbr> 48-51 (<a href="International_Standard_Serial_Number" title="International Standard Serial Number">ISSN</a> <a rel="nofollow" class="external text" href="https://portal.issn.org/resource/issn/1526-5463">1526-5463</a>, <a rel="nofollow" class="external text" href="http://www.eng.tau.ac.il/~ami/cd/or50/1526-5463-2002-50-01-0048.pdf">lire en ligne</a>)<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.atitle=Richard+Bellman+on+the+birth+of+Dynamic+Programming&rft.jtitle=Operations+Research&rft.issue=1&rft.aulast=Dreyfus&rft.aufirst=Stuart&rft.date=2002&rft.volume=50&rft.pages=48-51&rft.issn=1526-5463&rft_id=http%3A%2F%2Fwww.eng.tau.ac.il%2F~ami%2Fcd%2For50%2F1526-5463-2002-50-01-0048.pdf&rfr_id=info%3Asid%2Ffr.wikipedia.org%3AProgrammation+dynamique"></li></ul>

<dl><dt>Cours et notes de cours</dt></dl>

<ul><li><a href="Thomas_H._Cormen" title="Thomas H. Cormen">Thomas H. Cormen</a>, <a href="Charles_E._Leiserson" title="Charles E. Leiserson">Charles E. Leiserson</a>, <a href="Ronald_Rivest" title="Ronald Rivest">Ronald L. Rivest</a> et <a href="Clifford_Stein" title="Clifford Stein">Clifford Stein</a>, <cite class="italique"><a href="Introduction_%C3%A0_l'algorithmique" title="Introduction à l'algorithmique">Introduction à l'algorithmique</a></cite>, <a href="Dunod" class="mw-redirect" title="Dunod">Dunod</a>, <time>2002</time> [détail de l’édition]<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Introduction+%C3%A0+l%27algorithmique&rft.pub=Dunod&rft.aulast=Cormen&rft.aufirst=Thomas+H.&rft.au=Leiserson%2C+Charles+E.&rft.au=Rivest%2C+Ronald+L.&rft.au=Stein%2C+Clifford&rft.date=2002&rfr_id=info%3Asid%2Ffr.wikipedia.org%3AProgrammation+dynamique"> — Chapitre 15, « Programmation dynamique », pages 315-360.</li>

<li>« <a rel="nofollow" class="external text" href="http://openclassrooms.com/courses/introduction-a-la-programmation-dynamique"><cite style="font-style:normal;">Introduction à la programmation dynamique</cite></a> », sur openclassrooms.com, OpenClassrooms (consulté le <time class="nowrap" datetime="2015-02-21" data-sort-value="2015-02-21">21 février 2015</time>)</li>

<li>Robert Cori, « <a rel="nofollow" class="external text" href="http://dept-info.labri.u-bordeaux.fr/~cori/Enseirb/progDynamique.pdf"><cite style="font-style:normal;">Principe de la programmation dynamique</cite></a> », Enseirb (consulté le <time class="nowrap" datetime="2015-02-21" data-sort-value="2015-02-21">21 février 2015</time>).</li>

<li>Guillaume Carlier, « <a rel="nofollow" class="external text" href="https://www.ceremade.dauphine.fr/~carlier/progdyn.pdf"><cite style="font-style:normal;">Programmation dynamique - Notes de cours</cite></a> », ENSAE, <time>2007</time> (consulté le <time class="nowrap" datetime="2015-02-21" data-sort-value="2015-02-21">21 février 2015</time>).</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Annexes">Annexes</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Articles_connexes">Articles connexes</h3></div>

<ul><li><a href="Commande_optimale" title="Commande optimale">Commande optimale</a></li>

<li><a href="Automatique" title="Automatique">Automatique</a></li>

<li><a href="Diviser_pour_r%C3%A9gner_(informatique)" title="Diviser pour régner (informatique)">Diviser pour régner</a></li>

<li><a href="M%C3%A9mo%C3%AFsation" title="Mémoïsation">Mémoïsation</a></li>

<li><a href="D%C3%A9composition_arborescente" title="Décomposition arborescente">Décomposition arborescente</a></li>

<li><a href="Algorithme_glouton" title="Algorithme glouton">Algorithme glouton</a></li>

<li><a href="Algorithme_de_Viterbi" title="Algorithme de Viterbi">Algorithme de Viterbi</a></li>

<li><a href="Distance_de_Levenshtein" title="Distance de Levenshtein">Distance de Levenshtein</a></li>

<li><a href="Algorithme_de_Smith-Waterman" title="Algorithme de Smith-Waterman">Algorithme de Smith-Waterman</a></li>

<li><a href="Algorithme_de_Bellman-Ford" title="Algorithme de Bellman-Ford">Algorithme de Bellman-Ford</a></li>

<li><a href="Algorithme_de_Cocke-Younger-Kasami" title="Algorithme de Cocke-Younger-Kasami">Algorithme de Cocke-Younger-Kasami</a></li>

<li><a href="Probl%C3%A8me_du_sac_%C3%A0_dos" title="Problème du sac à dos">Problème du sac à dos</a></li>

<li><a href="Probl%C3%A8me_du_rendu_de_monnaie" title="Problème du rendu de monnaie">Problème du rendu de monnaie</a></li>

<li><a href="Probl%C3%A8me_du_voyageur_de_commerce" title="Problème du voyageur de commerce">Problème du voyageur de commerce</a></li>

<li><a href="Probl%C3%A8me_de_Jos%C3%A8phe" title="Problème de Josèphe">Problème de Josèphe</a></li>

<li><a href="Taux_d'erreur_de_mots" title="Taux d'erreur de mots">Taux d'erreur de mots</a></li>

<li><a href="Plus_longue_sous-s%C3%A9quence_commune" title="Plus longue sous-séquence commune">Plus longue sous-séquence commune</a></li>

<li><a href="FASTA_(programme_informatique)" title="FASTA (programme informatique)">FASTA (programme informatique)</a></li>

<li><a href="Distance_d'%C3%A9dition_sur_les_arbres" title="Distance d'édition sur les arbres">Distance d'édition sur les arbres</a></li>

<li><a href="Plus_petit_anc%C3%AAtre_commun" title="Plus petit ancêtre commun">Plus petit ancêtre commun</a></li>

<li><a href="Graphe_hamiltonien" title="Graphe hamiltonien">Graphe hamiltonien</a></li></ul>

</div>

</div>

<ul id="bandeau-portail" class="bandeau-portail"><li> Portail de l'informatique théorique </li> <li> Portail des mathématiques </li> </ul></div><div><div class="zim-footer">

Cet article est issu de <a class="external text" title="Dernière modification le 2024-06-27" href="https://fr.wikipedia.org/wiki/?title=Programmation_dynamique&oldid=216302582">Wikipédia</a>. Sauf mention contraire, le texte est disponible sous <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.fr">Creative Commons Attribution-Share Alike 4.0</a>. Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.

</div>

</div></div>

</div>

</main>

</div>

</body></html>